#include <bits/stdc++.h>

using namespace std;

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


// 此方法为普通bfs，此题不推荐
class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        if(!root) return {};

        vector<vector<int>> ret;
        queue<TreeNode*> q;
        unordered_map<TreeNode*, int> levels;
        q.push(root);
        levels[root] = 0;
        while(!q.empty())
        {
            TreeNode* cur = q.front();
            q.pop();
            int level = levels[cur];
            if(level == ret.size()) ret.push_back({});
            ret[level].emplace_back(cur->val);
            if(cur->left)
            {
                q.push(cur->left);
                levels[cur->left] = level + 1;
            }
            if(cur->right)
            {
                q.push(cur->right);
                levels[cur->right] = level + 1;
            }
        }

        return ret;
    }
};

// 此方法为每次处理一层的优化bfs，此题推荐
class Solution 
{
private:
    // 如果测试数据量变大了就修改这个值
    static const int MAXN = 2001;
    TreeNode* queue[MAXN];
    int l, r;

public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        if(!root) return {};

        vector<vector<int>> ret;
        l = r = 0;
        queue[r++] = root;
        while(l < r) // 队列里还有东西
        {
            int n = r - l;
            vector<int> v;
            while(n--)
            {
                TreeNode* t = queue[l++];
                v.push_back(t->val);
                if(t->left) queue[r++] = t->left;
                if(t->right) queue[r++] = t->right;
            }
            ret.emplace_back(v);
        }
        return ret;
    }
};